COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00004 00003	.BEGIN NOFILL
C00009 ENDMK
C⊗;
.device xgp
.EVENLEFTBORDER←ODDLEFTBORDER←1000
.require "pubmac[206, NXL]" source_file
.font 1 "basl30" <<text>>
.font 2 "bdr30" <<sym>>
.font 3 "basi30" <<var>>
.font 4 "basb30" <<bold>>
.font 5 "bdr30" <<const>>
.font 6 "sub"
.font 7 "sup"
.font A "fix40"
.font B "fix30"
.PAGE FRAME 52 HIGH 90 WIDE;
.AREA TEXT LINES 4 TO 50 CHARS 1 TO 83;
.TITLE AREA HEADING LINES 1 TO 3 CHARS 1 TO 83;
.TITLE AREA FOOTING LINE 51 CHARS 1 TO 83;
.PLACE TEXT;
.turn on "%#π" ;
.<<TURN ON "@" FOR "∂" ;>>
.every heading(, {SECNAME}, {page}) ;
.<<EVERY FOOTING(, {SECTION!}.{SUBSECTION!}, )>>
.AT 8 ⊂"%1        %*"⊃ ;
.AT 16 ⊂"%1                %*"⊃ ;
.<<AT "\→" KK "." ; ⊂KK ← CHAR⊃ ;>>
.BEGIN NOFILL
.VARIABLE CHW
.CHW ← CHARW
.TURN ON "←∂{%"
.TURN ON "/" FOR "α"
.AT "∂∂(" CH ")" ⊂ CHARW←CH}∂(2){CHARW←CHW ⊃
←%1CS206		SOLUTIONS TO HOMEWORK		FALL 1974
.TURN OFF "βα#\←∞↑↓∪"

.fill
%11.
∂∂(48)%3alt%2[%3u%2, %3m%2, %3n%2]%2 %2← %4if%2 %4n %3u%2 %4then%2 %5NIL%2 %4else if%2 %3m%2 %4eq %51%2 %4then%2 %4a %3u%2 %2. %3alt%2[%4d %3u%2, %3n%2, %3n%2]%2 %4else%2 %3alt%2[%4d %3u%2, %3sub1%2 %3m%2, %3n%2]
.nofill


%12.∂∂(48)%3odds%2 %3u%2 %2← %3odds1%2[%3u%2, %5NIL%2]

∂∂(48)%3odds1%2[%3u%2, %3v%2]%2 %2← %4if%2 %4n %3u%2 %4then%2 %3v%2 %4else%2 %3odds1%2[%4d %3u%2, %3enter%2[%4a %3u%2, %3v%2]%2]

∂∂(48)%3enter%2[%3x%2, %3v%2]%2 %2← %4if%2 %4n %3v%2 %4then%2 %2<%3x%2>%2 %4else if%2 %3equal%2[%4a %3v%2, %3x%2]%2 %4then%2 %4d %3v%2 %4else%2 %4a %3v%2 %2. %3enter%2[%3x%2, %4d %3v%2]


%13.∂∂(48)%3commontail%2[%3u%2, %3v%2]%2 %2← %3commonr%2[%3reverse%2 %3u%2, %3reverse%2 %3v%2, %5NIL%2]

∂∂(48)%3commonr%2[%3u%2, %3v%2, %3w%2]%2 %2← %4if%2 %4n %3u%2 %2∨ %4n %3v%2 %2∨ %2¬%3equal%2[%4a %3u%2, %4a %3v%2]%2 %4then%2 %3w%2 %4else%2 %3commonr%2[%4d %3u%2, %4d %3v%2, %4a %3u%2 %2. %3w%2]


%15.∂∂(48)%3rcycle%2 %3u%2 %2← %2/{%3reverse%2 %3u%2}%2[λ%3v%2. %4a %3v%2 %2. %3reverse%2 %4d %3v%2]

∂∂(48)%3lcycle%2 %3u%2 %2← %4d %3u%2 %2* %2<%4a %3u%2>


.fill
%16.  ∂∂(48)%3permut%2 %3u%2 %2← %4if%2 %4n %3u%2 %4then%2
%2(%5NIL%2)%2 %4else%2 %3permut1%2[%4a %3u%2, %3permut%2 %4d %3u%2]
.nofill

∂∂(48)%3permut1%2[%3x%2, %3w%2]%2 %2← %4if%2 %4n %3w%2 %4then%2 %5NIL%2 %4else%2 %3permut2%2[%5NIL%2, %3x%2, %4a %3w%2]%2 %2* %3permut1%2[%3x%2, %4d %3w%2]

∂∂(48)%3permut2%2[%3u%2, %3x%2, %3v%2]%2 %2← %4if%2 %4n %3v%2 %4then%2 %2<%3reverse%2 %3x%2 %2. %3u%2>%2 %4else%2 %3rev1%2[%3x%2 %2. %3u%2, %3v%2]%2 %2. %3permut2%2[%4a %3v%2 %2. %3u%2, %3x%2, %4d %3v%2]

∂∂(48)%3rev1%2[%3u%2, %3v%2]%2 %2← %4if%2 %4n %3u%2 %4then%2 %3v%2 %4else%2 %3rev1%2[%4d %3u%2, %4a %3u%2 %2. %3v%2]


%17.  (I assumed that the graph is represented in the same form as described for problem 8).
∂∂(48)%3conn%2 %3u%2 %2← %3comp%2 %3u%2 %2< %52


%18.∂∂(48)%3comp%2 %3u%2 %2← %3length%2 %3mergcomps%2 %3u

∂∂(48)%3mergcomps%2 %3u%2 %2← %4if%2 %4n %3u%2 %4then%2 %5NIL%2 %4else%2 %3mergcomp%2[%4aa %3u%2, %4a %3u%2, %3mergcomps%2 %4d %3u%2]

∂∂(48)%3mergcomp%2[%3x%2, %3c%2, %3l%2]%2 %2← 
∂∂(80)%4if%2 %4n %3l%2 %4then%2 %2<%3c%2>
∂∂(80)%4else if%2 %3x%2 %2ε %4a %3l%2 %4then%2 %3mergcomp%2[%3x%2, %3union%2[%3c%2, %4a %3l%2]%2, %4d %3l%2]
∂∂(80)%4else%2 %4a %3l%2 %2. %3mergcomp%2[%3x%2, %3c%2, %4d %3l%2]

∂∂(48)%3union%2[%3u%2, %3v%2]%2 %2← %4if%2 %4n %3u%2 %4then%2 %3v%2 %4else if%2 %4a %3u%2 %2ε %3v%2 %4then%2 %3union%2[%4d %3u%2, %3v%2]%2 %4else%2 %4a %3u%2 %2. %3union%2[%4d %3u%2, %3v%2]
.END